/*
 * @lc app=leetcode.cn id=887 lang=golang
 *
 * [887] 鸡蛋掉落
 */

// @lc code=start

import (
	"math"
)

// 最坏情况：需要遍历所有楼层
// 至少：选择最少的策略
// 也就是在当层鸡蛋是否碎，选最大消耗的选项
func superEggDrop(k int, n int) int {
	res := make([][]int, k+1)
	for i := 0; i < k+1; i++ {
		res[i] = make([]int, n+1)
	}

	// fmt.Println(res[1])
	// for i := 0; i < k+1; i++ {
	// 	for j := 0; j < n+1; j++ {
	// 		res[i][j] = math.MaxInt32
	// 	}
	// }
	dp(k, n, &res)
	return res[k][n]
}

func dp(K, N int, res *[][]int) int {
	// fmt.Println("1111", *res)
	if K == 1 {
		(*res)[K][N] = N
		return N
	}
	if N == 0 {
		(*res)[K][N] = 0
		return 0
	}
	if (*res)[K][N] != 0 {
		return (*res)[K][N]
	}
	(*res)[K][N] = math.MaxInt32
	l, r := 1, N
	for l <= r {
		mid := (l + r) / 2
		// fmt.Println("-----", res)
		up := dp(K, N-mid, res)   // 没碎
		lo := dp(K-1, mid-1, res) // 碎了
		// (*res)[K][N] = min((*res)[K][N], max(dp(K, N-i, res), dp(K-1, i-1, res))+1)
		if up > lo {
			(*res)[K][N] = min((*res)[K][N], up+1)
			l = mid + 1
		} else {
			(*res)[K][N] = min((*res)[K][N], lo+1)
			r = mid - 1
		}
	}
	return (*res)[K][N]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

// @lc code=end
